package cxydmmszl.chapter08.t143;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;

/**
 * <li style="color: red;">Prob</li>
 * 大楼轮廓问题
 * <li style="color: green;">Desc</li>
 * 给定一个 N×3 的矩阵 matrix，对于每一个长度为 3 的小数组 arr，都表示一个大楼的三个数据。
 * arr[0] 表示大楼的左边界，arr[1] 表示大楼的右边界，arr[2] 表示大楼的高度(一定大于0)。
 * 每座大楼的地基都在 X 轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(NlogN)
 * <li style="color: green;">Input</li>
 * 第一行一个整数 N，表示大楼的数量。
 * 接下来 N 行，每个三个整数，表示第 i 个大楼的信息。
 * <li style="color: green;">Output</li>
 * 输出若干行，每行有 3 个整数，表示最终的轮廓线。
 * <li style="color: blue;">Link</li> CD52
 *
 * @author habitplus
 * @since 2021-10-17 18:24
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (IOException e) {
            throw new RuntimeException("input is invalid");
        }
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[][] arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            arr[i][0] = nextInt();
            arr[i][1] = nextInt();
            arr[i][2] = nextInt();
        }

        ArrayList<int[]> list = buildingOutline(arr);
        StringBuilder sb = new StringBuilder();
        for (int[] e : list) {
            sb.append(e[0]).append(' ')
                    .append(e[1]).append(' ')
                    .append(e[2]).append('\n');
        }
        System.out.println(sb.toString());
    }

    static class Elem {
        int x; // x 轴上的值
        boolean isAdd; // 加入 or 删除
        int height;

        public Elem(int x, int height, boolean isAdd) {
            this.x = x;
            this.height = height;
            this.isAdd = isAdd;
        }
    }

    private static ArrayList<int[]> buildingOutline(int[][] b) {
        if (b == null || b.length == 0 || b[0].length != 3) {
            return new ArrayList<>();
        }

        int n = b.length;
        // 将楼层数据预处理成高度变化的数据
        Elem[] hcs = new Elem[2 * n];
        for (int i = 0; i < n; i++) {
            hcs[i * 2] = new Elem(b[i][0], b[i][2], true);
            hcs[i * 2 + 1] = new Elem(b[i][1], b[i][2], false);
        }

        // 排序：优先按 x 的值升序排列，相同则【添加】排在前面
        Arrays.sort(hcs, (o1, o2) -> {
            if (o1.x != o2.x) return o1.x - o2.x;
            if (o1.isAdd != o2.isAdd) return o1.isAdd ? -1 : 1;
            return 0;
        });

        // key = 当前高度，value = 当前高度出现的次数
        TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>();
        // key : 当前的 x 轴的值，value = 当前已存在的高度的最大值
        TreeMap<Integer, Integer> mapXvalueHeight = new TreeMap<>();
        int times, h;
        for (int i = 0; i < hcs.length; i++) {
            h = hcs[i].height;
            if (hcs[i].isAdd) {
                // 当前是加入操作
                times = mapHeightTimes.getOrDefault(h, 0);
                mapHeightTimes.put(h, times + 1);
//                if (!mapHeightTimes.containsKey(h)) {
//                    mapHeightTimes.put(h, 1);
//                } else {
//                    times = mapHeightTimes.get(h);
//                    mapHeightTimes.put(h, times + 1);
//                }
            } else {
                // 删除操作
                if ((times = mapHeightTimes.get(h)) > 1) {
                    // 当前高度出现不止一次
                    mapHeightTimes.put(h, times - 1);
                } else {
                    // 当前高度只出现一次
                    mapHeightTimes.remove(h);
                }
            }

            // 根据 mapHeightTimes 中的最大高度，更新当前位置的最大高度 mapXvalueHeight
            if (mapHeightTimes.isEmpty()) {
                mapXvalueHeight.put(hcs[i].x, 0);
            } else {
                // lastKey() 返回的是当前存在的最大高度
                mapXvalueHeight.put(hcs[i].x, mapHeightTimes.lastKey());
            }
        }

        // 根据 mapXvalueHeight 生成 res
        ArrayList<int[]> res = new ArrayList<>();
        int start = 0;
        int preH = 0;
        int curX, curH;
        for (Map.Entry<Integer, Integer> e : mapXvalueHeight.entrySet()) {
            curX = e.getKey();
            curH = e.getValue();
            if (preH != curH) {
                // 之前的高度和当前高度不一致，说明轮廓线出现了
                // 这里还要排除前一个高度为 0 的情况
                if (preH != 0) {
                    res.add(new int[]{start, curX, preH});
                }
                start = curX;
                preH = curH;
            }
        }

        return res;
    }
}
